#pragma once

#include <string>
	
	template <class K>
	class BSTree
	{
		typedef BSTreeNode<K> Node;
	private:
		Node* copytree(Node* root)
		{
			if (root == nullptr)
				return nullptr;
			Node* node = new Node(root->_key);
			node->_left = copytree(root->_left);
			node->_right = copytree(root->_right);
			return node;
		}

		void Destory(Node* root)
		{
			if (root == nullptr)
				return;
			Destory(root->_left);
			Destory(root->_right);
			delete root;
		}
	public:
		BSTree() = default;

		BSTree(const BSTree<K>& t)
		{
			_root=copytree(t._root);
		}

		BSTree<K>& operator=(BSTree<K> t)
		{
			swap(_root, t._root);
			return *this;
		}

		~BSTree()
		{
			Destory(_root);
			_root = nullptr;
		}

		void InorderR()
		{
			_InorderR(_root);
			cout << endl;
		}

		bool FindR(const K& key)
		{
			return _FindR(_root, key);
		}

		bool InsertR(const K& key)
		{
			return _InsertR(_root, key);
		}

		bool EraseR(const K& key)
		{
			return _EraseR(_root, key);
		}
	private:
		bool _EraseR(Node*& root, const K& key)
		{
			if (root == nullptr)
				return false;
			if (root->_key > key)
				return _EraseR(root->_left, key);
			else if (root->_key < key)
				return _EraseR(root->_right, key);
			else
			{
				Node* del = root;
				if (root->_left == nullptr)
					root = root->_right;
				else if (root->_right == nullptr)
					root = root->_left;
				else
				{
					Node* minright = root->_right;
					while (minright->_left)
						minright = minright->_left;
					swap(root->_key, minright->_key);

					//_EraseR(root->_right, key);
					return _EraseR(root->_right, key);
				}

				delete del;
				return true;
			}
			return false;
		}

		bool _InsertR(Node*& root, const K& key)
		{
			if (root == nullptr)
			{
				root = new Node(key);
				return true;
			}
			if (root->_key > key)
				return _InsertR(root->_left, key);
			else if (root->_key < key)
				return _InsertR(root->_right, key);
			else
				return false;
		}

		bool _FindR(Node* root, const K& key)
		{
			if (root == nullptr)
				return false;
			if (root->_key > key)
				return _FindR(root->_left, key);
			else if (root->_key < key)
				return _FindR(root->_right, key);
			else
				return true;
		}

		void _InorderR(Node* root)
		{
			if (root == nullptr)
				return;
			_InorderR(root->_left);
			cout << root->_key << " ";
			_InorderR(root->_right);
		}

		Node* _root = nullptr;
	};

	void TestBSTree1()
	{
		BSTree<int> d;
		int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
		for (auto& e : a)
		{
			d.InsertR(e);
		}
		d.InorderR();

		BSTree<int> t(d);
		t.InorderR();

		BSTree<int> m;
		m = t;
		m.InorderR();

		cout << d.FindR(41) << endl;

		d.EraseR(3);
		d.EraseR(7);
		d.InorderR();

		d.EraseR(10);
		d.EraseR(14);
		d.InorderR();
		for (auto& e : a)
		{
			d.EraseR(e);
		}
		d.InorderR();

		
	}
}